package cn.edu.ncepu;

import java.util.ArrayList;
import java.util.List;

public class SubsetGenerator {

    /**
     * 根据位掩码从输入列表中筛选元素生成子集
     * @param input 原始列表
     * @param mask 位掩码（二进制位表示元素是否被选中）
     * @return 生成的子集
     * @param <T> 元素类型
     */
    public static <T> List<T> fromMask(List<T> input, int mask) {
        List<T> result = new ArrayList<>();
        for (int i = 0; i < input.size(); i++) {
            // 判断第i位是否为1：(1 << i) & mask != 0
            if (((1 << i) & mask) != 0) {
                result.add(input.get(i));
            }
        }
        return result;
    }

    /**
     * 生成输入列表的所有子集（基于位掩码）
     * @param input 原始列表
     * @return 所有子集的列表
     * @param <T> 元素类型
     */
    public static <T> List<List<T>> subsets(List<T> input) {
        int n = input.size();
        int totalSubsets = 1 << n; // 2^n 个子集
        List<List<T>> allSubsets = new ArrayList<>(totalSubsets);

        // 遍历所有掩码（0 到 2^n - 1）
        for (int mask = 0; mask < totalSubsets; mask++) {
            allSubsets.add(fromMask(input, mask));
        }

        return allSubsets;
    }

    public static void main(String[] args) {
        // 测试：生成[1,2,3]的所有子集
        List<Integer> input = List.of(1, 2, 3);
        List<List<Integer>> result = subsets(input);

        // 输出结果，格式与Python一致
        System.out.println(result);
    }
}